package com.fw.leetcode.binarysearch;

import com.fw.leetcode.LeetCode;

import java.util.Random;

/**
 * 162. Find Peak Element
 *
 * A peak element is an element that is strictly greater than its neighbors.
 *
 * Given a 0-indexed integer array nums, find a peak element, and return its index.
 * If the array contains multiple peaks, return the index to any of the peaks.
 *
 * You may imagine that nums[-1] = nums[n] = -∞. In other words,
 * an element is always considered to be strictly greater than a neighbor that is outside the array.
 *
 * You must write an algorithm that runs in O(log n) time.
 *
 * Example 1:
 *  Input: nums = [1,2,3,1]
 *  Output: 2
 *  Explanation: 3 is a peak element and your function should return the index number 2.
 *
 * Example 2:
 *  Input: nums = [1,2,1,3,5,6,4]
 *  Output: 5
 *  Explanation: Your function can return either index number 1 where the peak element is 2,
 *  or index number 5 where the peak element is 6.
 *
 * Constraints:
 *  1 <= nums.length <= 1000
 *  -2^31 <= nums[i] <= 2^31 - 1
 *  nums[i] != nums[i + 1] for all valid i.
 */
public class Num_0162 implements LeetCode {

    private interface Solution {
        int findPeakElement(int[] nums);

        default void assertExpected(int[] nums, int expected) {
            if (findPeakElement(nums) != expected) {
                findPeakElement(nums);
            }
        }
    }

    private static class MaxSolution implements Solution {

        @Override
        public int findPeakElement(int[] nums) { // 求最大值，时O(n) 空O(1)，不满足题目要求的时O(log n)
            int max = nums[0];
            int index = 0;
            for (int i = 1; i < nums.length; i++) {
                if (max < nums[i]) {
                    max = nums[i];
                    index = i;
                }
            }
            return index;
        }
    }

    private static class ClimbSolution implements Solution {

        @Override
        public int findPeakElement(int[] nums) { // 随机爬峰，时O(n) 空O(1)
            /*
             * 假定两侧边界值比边界外都大
             *           /\
             *        /\/  \_   _          _
             *       /       \_/ \_   _   / \_
             *     _/              \_/ \_/     \
             *   /
             */
            // 随机一点开始爬峰
            int idx = new Random().nextInt(nums.length - 1);
            while (!(compare(nums, idx - 1, idx) < 0 && compare(nums, idx, idx + 1) > 0)) { // 峰顶
                // 非峰顶时（峰谷或斜坡）
                if (compare(nums, idx, idx + 1) < 0) {
                    idx += 1; // 向右上爬（含峰谷时任意选择向右上爬）
                } else {
                    idx -= 1; // 向左上爬
                }
            }
            return idx;
        }

        private int compare(int[] nums, int idx1, int idx2) {
            if (idx1 < 0) { // 边界条件：数组索引外的数据统一小于边界值
                return -1; // idx1 < idx2
            } else if (idx2 > nums.length - 1) {
                return 1; // idx1 > idx2
            } else {
                return Integer.compare(nums[idx1], nums[idx2]);
            }
        }
    }

    private static class BinarySearchSolution implements Solution {

        @Override
        public int findPeakElement(int[] nums) { // 随机爬峰 + 二分，时O(log n) 空O(1)
            /*
             * 假定两侧边界值比边界外都大
             *           /\
             *        /\/  \_   _          _
             *       /       \_/ \_   _   / \_
             *     _/              \_/ \_/     \
             *   /
             */
            // 随机一点开始爬峰
            int left = 0;
            int right = nums.length - 1;
            int mid = 0;
            while (left <= right) {
                mid = (left + right) / 2;
                if (compare(nums, mid - 1, mid) < 0 && compare(nums, mid, mid + 1) > 0) {
                    break; // 峰顶
                }
                // 非峰顶时（峰谷或斜坡）
                if (compare(nums, mid, mid + 1) < 0) {
                    left = mid + 1; // 向右上爬（含峰谷时任意选择向右上爬）
                } else {
                    right = mid - 1; // 向左上爬
                }
            }
            return mid;
        }

        private int compare(int[] nums, int idx1, int idx2) {
            if (idx1 < 0) { // 边界条件：数组索引外的数据统一小于边界值
                return -1; // idx1 < idx2
            } else if (idx2 > nums.length - 1) {
                return 1; // idx1 > idx2
            } else {
                return Integer.compare(nums[idx1], nums[idx2]);
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new BinarySearchSolution();
        solution.assertExpected(new int[]{1,2,3,1}, 2);
        solution.assertExpected(new int[]{1,2,1,3,5,6,4}, 5);
    }
}
